fn main() {
    println!("Hello, world!");
}
// The API isBadVersion is defined for you.
// isBadVersion(versions:i32)-> bool;
// to call it use self.isBadVersion(versions)
struct Solution;
impl Solution {
    pub fn first_bad_version(&self, n: i32) -> i32 {
		let mut left = 0;
        let mut right = n;
        let mut mid;
        while left <= right {
            mid = left + ((right - left) >> 1);
            if self.isBadVersion(mid) {
                right = mid - 1;
            } else {
                mid += 1;
                if self.isBadVersion(mid) {
                    return mid;
                } else {
                    left = mid;
                }
            }
        }
        return -1;
    }
}